Tree-based differential evolution algorithm for QoS multicast routing

doi:10.1016/S1005-8885(10)60087-8

中国邮电高校学报(英文) ›› 2011, Vol. 18 ›› Issue (4): 76-81.doi: 10.1016/S1005-8885(10)60087-8

Tree-based differential evolution algorithm for QoS multicast routing

孔笋,陈增强

南开大学

收稿日期:2010-12-07 修回日期:2011-04-01 出版日期:2011-08-31 发布日期:2011-08-24
通讯作者: 孔笋 E-mail:ksuser@mail.nankai.edu.cn

Tree-based differential evolution algorithm for QoS multicast routing

Received:2010-12-07 Revised:2011-04-01 Online:2011-08-31 Published:2011-08-24
Supported by:
This work was supported by the National Natural Science Foundation of China (60774088); the Hi-Tech Research and Development Program of China (2009AA04Z132); the Specialized Research Foundation for the Doctoral Program of National Education Ministry (20090031110029).

摘要/Abstract

摘要：

Differential evolution (DE) algorithm has attracted more and more attention due to its fast optimization performance and good stability. When DE algorithm is applied into multi-constrained multicast routing optimization problem, a common solution to such problem is to merge the paths into a tree after finding paths from the source node to each destination node. This method maybe obtains the better result, but it can consume a lot of computational time. To solve the problem, a tree-based DE algorithm is introduced in this paper. The central operations of the algorithm are realized with tree structure. This method saves the time of finding paths and integrating them to construct a multicast tree. The experiments show that the proposed algorithm can achieve higher success rate than several common algorithms with much smaller running time for different networks.

关键词:

quality of service (QoS), multicast routing, DE, tree structure

Abstract:

Key words:

quality of service (QoS), multicast routing, DE, tree structure

中图分类号:

TN949.291

KONG Sun, CHEN Zeng-qiang. Tree-based differential evolution algorithm for QoS multicast routing[J]. Acta Metallurgica Sinica(English letters), 2011, 18(4): 76-81.

参考文献

1. Wang Z, Crowcroft J. Quality of service for supporting multimedia applications. IEEE Journal on Selected Areas in Communications, 1996, 14(7): 1228-1234

2. Shimamoto N, Hiramatu A, Yanmasaki K. A dynamic routing control based on a genetic algorithm. Proceedings of the IEEE International Conference on Neural Networks (ICNN’93): Vol 2, Mar 28-Apr 1, 1993, San Francisco, CA, USA. Piscatawaw, NJ, USA: IEEE, 1993: 1123-1128

3. Sun W S, Liu Z M. Multicast routing based neural networks. Journal of China Institute of Communications, 1998, 19(11): 1-6 (in Chinese)

4. Randaccio S L, Atzori L. Group multicast routing problem: a genetic algorithms based approach. Computer Networks, 2007, 51(14): 3989-4004

5. Nesmachnow S, Cancela H, Alba E. Evolutionary algorithms applied to reliable communication network design. Engineering Optimization, 2007, 39(7): 831-855

6. Zahrani M S, Loomes M J, Maicolm J A, et al. A local search heuristic for bounded-degree minimum spanning trees. Engineering Optimization, 2008, 40(12): 1115-1135

7. Ma X, Chen Q, Hisakazu O, et al. Genetic algorithm for the multiple-origins-multiple-destinations routing problem. Journal of Computational Information Systems, 2008, 4(1): 257-262

8. Fei X, Luo J Z, Wu J Y, et al. QoS Routing based on genetic algorithm. Computer Communications, 1999, 22(9): 1394-1399

9. Hwang R H, Do W Y, Yang S C. Multicast routing based on genetic algorithms. Journal of Information Science and Engineering, 2000, 16(5): 885-901

10. Wang Z Y, Shi B X, Zhao E D. Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm. Computer Communications, 2001, 24(7): 685-692

11. Wang Y, Xie J Y. Ant colony optimization for multicast routing. Proceedings of the IEEE Asia Pacfic Conference on Circuits and Systems (APCCAS’00), Dec 4-6, 2000, Tianjin, China. Piscataway, NJ, USA: IEEE, 2000: 54-57

12. Chu C H, Gu J H, Hou X D, et al. A heuristic ant algorithm for solving QoS multicast routing problem. Proceedings of the 2002 Congress on Evolutionary Computation (CEC’02): Vol 2, May 12-17, 2002, Honolulu, HI, USA. Piscataway, NJ, USA: IEEE, 2002: 1630-1635

13. Wang H, Shi Z, Ma J, et al. The tree-based ant colony algorithm for multi-constraints multicast routing. Proceedings of the 9th International Conference on Advanced Communication Technology (ICACT’07): Vol 3, Feb 12-14, 2007, Seoul, Republic of Korea. Piscataway, NJ, USA: IEEE, 2007: 1544-1547

14. Liu J, Sun J, Xu W B. QoS multicast routing based on particle swarm optimization. Proceedings of the 7th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL’06), Sep 20-23, 2006, Burgos, Spain. LNCS 4224. Berlin, Germany: Springer-Verlag, 2006: 936-943

15. Jin X, Bai L, Ji Y F, et al. Probability convergence based particle swarm optimization for multiple constrained QoS multicast routing. Proceedings of the 4th International Conference on Semantics, Knowledge and Grid (SKG’08), Dec 3-5, 2008, Beijing, China. Los Alamitos, CA, USA: IEEE Computer Society, 2008: 412-415

16. Storn R, Price K. Differential evolution--A simple and efficient heuristic for global optimization over continuous spaces. Journal of Global Optimization,1997, 11 (4) 341-359

17. Xie X F, Zhang W J, Zhang G R. Empirical study of differential evolution. Control and Decision, 2004, 19(1): 49-52, 56 (in Chinese)

18. Vesterstrom J, Thomsen R. A comparative study of differential evolution particle swarm optimization and evolutionary algorithms on numerical benchmark problem. Proceedings of the 2004 Congress on Evolutionary Computation (CEC’04): Vol 2, Jun 19-23, 2004, Portland, OR, USA. Piscataway, NJ, USA: IEEE, 2004: 1980-1987

19. Onwubolu G C, Babu B V. New optimization techniques in engineering. Berlin, Germany: Springer-Verlag, 2004

20. Yang Q W, Jiang J P, Qu C X, et al. Improving genetic algorithms by using logic operation. Control and Decision, 2000, 15(4): 510-512 (in Chinese)

21. Waxman B M. Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 1988, 6(9): 1617-1622

Tree-based differential evolution algorithm for QoS multicast routing

Tree-based differential evolution algorithm for QoS multicast routing

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价